/**************************************************************************************************

RTree Brainstorm and Implementation Plan

Basic Strucuture: 

Node hierarchy: trunks > non-leafs > leafs
Node structure: MBR (Maximum Bounding Rectangle) and children nodes if it is a non-leaf node

Functions:
	Insert
		node resize/add
	Delete
		node resize/merge/delete
	Search
	
R*Tree: 
	Same deletion and searching as normal RTree; however insertion is slightly different.
	Upon insertion, a proper node is found for placement of the point.
	A selection from this node is then reinserted along with the given point.
	Reinsertion may require resizing, merging, and/or adding nodes.
	Because of continual reinsertion, the R*Tree incrementally gains performance.
	Chronic resizing and rebuilding is thus unneccesary.
	
gcc -o rtree rTree3D.c 
	
***************************************************************************************************/

#include <rTreeLL.h>
#include <vector3D.h>
#include <boid.h>

#define MAXBD		4		/*maximum number of boids in each node*/	
#define MAXCHLD		3		/*maximum number of child nodes*/

typedef struct rect3D {
	vector3D negative, positive;
}

typedef struct nodeRTree {
	Boid* boids[MAXBD + 1]; /*array of pointers containing unsorted boids*/
	int bdcnt; /*number of boids in the node*/
	
	struct nodeRTree children[MAXCHLD + 1]; /*child nodes*/
	int chldcnt; /*number of children*/
	
	int leaf; /*essentially a boolean that determines whether or not the node is a leaf i.e. has no children*/
	
	rect3D mbr; /*the maximum bounding rectangle which contains all of the node's boids'*/
}

nodeRTree initRTree() {
	nodeRTree newTree;
	newTree.leaf = 1; /*new tree is empty and thus must be a leaf*/
	return newTree;
}

int pointInRect(rect3D *rect, vector3D point) {
	return ((rect->negative.x < point.x) &&
	        (point.x < rect->positive.x) &&
	        (rect->negative.y < point.y) &&
	   		(point.y < rect->positive.y) &&
	   		(rect->negative.z < point.z) &&
	   		(point.z < rect->positive.z));
}

int overlapping(rect3D *first, rect3D *second) {
	return (((first->negative.x < second->negative.x) &&
			 (second->negative.x < first->positive.x) &&
			 (first->negative.y < second->negative.y) &&
			 (second->negative.y < first->positive.y) &&
			 (first->negative.z < second->negative.z) &&
			 (second->negative.z < first->positive.z))
			||
			((second->negative.x < first->negative.x) &&
			 (first->negative.x < second->positive.x) &&
			 (second->negative.y < first->negative.y) &&
			 (first->negative.y < second->positive.y) &&
			 (second->negative.z < first->negative.z) &&
			 (first->negative.z < second->positive.z)));
}

/*finds nodes which the given queryBox would overlap*/
/*TODO: optimize*/
nodeRTree* findNodes(nodeRTree *node, rect3D queryBox, rTreeLL* destination) {
	if((node->leaf) && (overlapping(queryBox, node->mbr))) {
		return node;
	} else {
		int i;
		for(i = 0; i < node->chldcnt; i++) {
			addNodeRTLL(destination, findNodes(&(node->children[i]), queryBox, destination));
		}
	}
}

/*inserts the given boid into a child of the given trunk node*/
/*placement is based on position of the MBR and number of boids in the node*/
/*TODO: consider amount the node would have to be resized*/
/*TODO: optimize*/
void insert(nodeRTree* trunk, Boid* boid) {
	rTreeLL possibleNodes;
	rect3D boidLoc;
	boidLoc.positive = boid.location;
	boidLoc.negative = boid.location;
	findNodes(trunk, boidLoc, possibleNodes);
	Node *currentNode = possibleNodes.root;
	nodeRTree *optimalNode;
	int minBoids = 0;
	int end = (currentNode.value == NULL);
	while(!end) {
		if(currentNode.value.bdcnt > minBoids) {
			minBoids = currentNode.value.bdcnt;
			optimalNode = currentNode;
		}
		end = (currentNode.value == NULL);
	}
}

/*Boid*[] rectSearch(nodeRTree* trunk, rect3D* searchArea) {*/
/*	*/
/*} */









